/**
 * //给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 * //
 * // 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * //
 * //输入: s = "cbaebabacd", p = "abc"
 * //输出: [0,6]
 * //解释:
 * //起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * //起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 * //
 * //
 * // 示例 2:
 * //
 * //
 * //输入: s = "abab", p = "ab"
 * //输出: [0,1,2]
 * //解释:
 * //起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
 * //起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
 * //起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
 * //
 * //
 * //
 * //
 * // 提示:
 * //
 * //
 * // 1 <= s.length, p.length <= 3 * 10⁴
 * // s 和 p 仅包含小写字母
 * //
 * //
 * // Related Topics 哈希表 字符串 滑动窗口 👍 1007 👎 0
 */

package com.xixi.basicAlgroithms.dualPointer;

import java.util.*;

public class ID00438FindAllAnagramsInAString {
    public static void main(String[] args) {
        Solution solution = new ID00438FindAllAnagramsInAString().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {

            if (s.length() < p.length()) return Collections.emptyList();

            List<Integer> resList = new ArrayList<>();


            char[] pCharArray = p.toCharArray();
            char[] sCharArray = s.toCharArray();

            Map<Character, Integer> pMap = new HashMap<>();
            for (int pi = 0; pi < p.length(); pi++) {
                Integer count = pMap.putIfAbsent(pCharArray[pi], 1);
                if (count != null) {
                    pMap.put(pCharArray[pi], count + 1);
                }
            }

            //findStartPoint
            int i = 0;
            int j = 0;
            while (j < s.length()) {

                //遇到不包含的字母就跳
                if (!pMap.containsKey(sCharArray[j])) {
                    i = j + 1;
                    j++;
                    continue;
                }

                int nowL = j - i + 1;
                if (nowL == p.length()) {
                    if (judgeAnagram(sCharArray, i, j, pMap)) { //如果是异位词
                        resList.add(i);
                    }
                    i++;
                    j++;
                } else if (nowL < p.length()) {
                    j++;
                } else {
                    i++;
                }


            }


            return resList;


        }

        public boolean judgeAnagram(char[] sCharyArray, int start, int end, Map<Character, Integer> pMap) {

            Map<Character, Integer> sMap = new HashMap<>();

            for (int si = start; si <= end; si++) {
                Integer count = sMap.putIfAbsent(sCharyArray[si], 1);
                if (count != null) {
                    sMap.put(sCharyArray[si], count + 1);
                }
            }

            for (char c : sMap.keySet()) {
                if (!pMap.get(c).equals(sMap.get(c))) return false;
            }
            return true;

        }

    }
//leetcode submit region end(Prohibit modification and deletion)


}